package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

/**
 * https://leetcode.com/problems/jump-game/
 * 判断是否能到达终点
 * see LC45
 * <p>
 * TODO 这题又可以回溯又可以DP又可以贪心?? https://leetcode.com/problems/jump-game/solution/
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC55 implements Greedy {
    public boolean canJump(int[] nums) {
        if (nums.length <= 1) return true;
        int lastIndexCanJump = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {//从数组后面倒着来
            if (nums[i] >= lastIndexCanJump - i) {
                lastIndexCanJump = i;
            }
        }
        return lastIndexCanJump == 0;
    }

    public static void main(String[] args) {
        System.out.println(new LC55().canJump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(new LC55().canJump(new int[]{3, 2, 1, 0, 4}));
    }
}
